package main

type UnionFind struct {
	parent, size []int
	count        int
}

func (uf *UnionFind) Init(n int) {
	uf.count = n
	uf.parent = make([]int, n)
	uf.size = make([]int, n)

	for i := range uf.parent {
		uf.parent[i] = i
		uf.size[i] = 1
	}
}

func (uf *UnionFind) Find(p int) int {
	root := p
	for root != uf.parent[root] {
		uf.parent[root] = uf.parent[uf.parent[root]]
		root = uf.parent[root]
	}

	return root
}

func (uf *UnionFind) Union(p, q int) {
	proot := uf.Find(p)
	qroot := uf.Find(q)
	if qroot == proot {
		return
	}

	if uf.size[qroot] > uf.size[proot] {
		uf.parent[proot] = qroot
		uf.size[qroot] += uf.size[proot]
	} else {
		uf.parent[qroot] = proot
		uf.size[proot] += uf.size[qroot]
	}
	uf.count--
}

func (uf *UnionFind) IsConnected(p, q int) bool {
	return uf.Find(q) == uf.Find(q)
}

func (uf *UnionFind) Count() int {
	return uf.count
}
